package com.wxweven.algorithm.list;

import java.util.Comparator;
import java.util.PriorityQueue;

public class LC23合并K个有序的单链表 {

    /*
     * 算法思想，使用优先队列(类似于小顶堆，堆顶元素是最小的)
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x.val));

        for (ListNode listNode : lists) {
            if (listNode != null) {
                pq.offer(listNode);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (!pq.isEmpty()) {
            ListNode top = pq.poll();
            cur.next = top;
            cur = top;
            if (top.next != null) {
                pq.offer(top.next);
            }
        }

        return dummy.next;
    }
}



